package leetcode.code0216;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public List<List<Integer>> combinationSum3(int k, int n) {
		List<List<Integer>> ans = new ArrayList<>();
		if (k < 2 || k > 9 || n < this.min(k) || n > this.max(k)) {
			return ans;
		}
		List<Integer> temp = new ArrayList<>();
		this.f(n, k, 1, 0, ans, temp);
		return ans;
	}

	private void f(int n, int k, int start, int sum, List<List<Integer>> ans, List<Integer> temp) {
		if (k == 0 || sum == n) {
			if (k == 0 && sum == n) {
				ans.add(new ArrayList<>(temp));
			}
			return;
		}
		for (int i = start; i <= 9 && i <= 10 - k; i++) {
			temp.add(i);
			this.f(n, k - 1, i + 1, sum + i, ans, temp);
			temp.remove(temp.size() - 1);
		}
	}

	private int min(int k) {
		return (1 + k) * k / 2;
	}

	private int max(int k) {
		return (19 - k) * k / 2;
	}

	@Override
	public void debug1() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,2,4]]");
		HelpDebug.compare(e, this.combinationSum3(3, 7));

	}

	@Override
	public void debug2() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,2,6],[1,3,5],[2,3,4]]");
		HelpDebug.compare(e, this.combinationSum3(3, 9));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
